# coding=utf-8

"""
Huffman编码是一种用最小长度对信息编码的方法。
没有任何字符的编码是其他编码的前缀。这样的编码称为前缀码（英文为preﾞx-code，
读者可能会奇怪为何它不叫无前缀码non-preﾞx code）。
使用前缀码，我们不需要任何分隔符。这样编码的长度就可以缩短。

这自然引发了一个有趣的问题：给定一个文本，我们能否找到一个码表，使
得编码长度最短？

这一方法的思路是根据字符在文本中出现的频率构造码表。最常用字符的编码最短。
首先可以处理文本，获得每个字符出现的次数。这样我们就有了一个字符
集，每个字符都有一个权重。权重为一个表示该字符出现频率的一个数字，它
可以是出现的次数，或者是出现的概率。

Huffman发现，可以使用一棵二叉树来产生前缀码。所有的字符都保存在叶
子节点。通过从根节点遍历树产生编码。当向左前进时，我们添加一个0，向右
前进时，添加一个1。

我们需要从一个字符及其权重的列表，构造一棵二进制树，使得最大权重
的字符，距离根节点的最近。Huffman提出了一个自底向上的解法。开始的时
候，所有的字符都放入一个叶子节点中。每次我们选出两个权重最小的节点，
然后把它们合并成一个分支节点。分支的权重为两个子树的权重和。我们不断
选择权重最小的两棵树合并，直到最后得到一棵树。
"""

'''
Huffman编码，特别是Huffman树的构造过程展示了一种有趣的策略。每次
合并都有若干选项。Huffman的方法总是从树中选取权重最小的两棵树。这是
合并阶段的最好选择。特别地，这一系列局部最优的选择，产生了一个全局最优的前缀编码。

但并非局部最优选择总能带来全局最优解。在大多数情况下并非如此。
Huffman编码是一个特殊情况。我们称这种每次选择局部最优选项的策略
为贪心策略。
'''


class Node:
    def __init__(self, weight, key=None):
        self.weight = weight
        self.key = key
        self.left = None
        self.right = None

    def setLeft(self, left):
        self.left = left

    def setRight(self, right):
        self.right = right

    def getLeft(self):
        return self.left

    def getRight(self):
        return self.right


def getMinTwo(nodelist: list):
    """
    取得列表中的最小weight的两个节点
    :param nodelist:
    :return:(min0,min1)
    """
    if len(nodelist) < 2:
        return None
    elif len(nodelist) == 2:
        return (nodelist.pop(0), nodelist.pop(0)) if nodelist[0].weight < nodelist[1].weight else (nodelist.pop(
            1), nodelist.pop(0))
    else:
        # 遍历获取weight最小的两个
        min_index = 0
        for i, node in enumerate(nodelist):
            if node.weight < nodelist[min_index].weight:
                min_index = i
        min0 = nodelist.pop(min_index)
        min_index = 0
        for i, node in enumerate(nodelist):
            if node.weight < nodelist[min_index].weight:
                min_index = i
        min1 = nodelist.pop(min_index)
        print('min two: key %s , %s; weight %s %s' % (min0.key, min1.key, min0.weight, min1.weight))
        return min0, min1


# 合并两个节点到一个新的分支节点
def merge(na: Node, nb: Node):
    parent = Node(na.weight + nb.weight, '(Parent of %s && %s)' % (na.key, nb.key))
    parent.setLeft(na)
    parent.setRight(nb)
    return parent


def build(nodelist: list):
    # 循环直到合并为一个节点
    while len(nodelist) > 1:
        (a, b) = getMinTwo(nodelist)
        nodelist.append(merge(a, b))
        print(len(nodelist))
    return nodelist.pop(0)


'''
可以使用小根堆来存储节点，这样每次取得的节点都是权值最小的，合并后的节点再插入到堆中。
'''

if __name__ == '__main__':
    nodes = [Node(2, 'A'), Node(3, 'N'), Node(2, 'T'), Node(1, 'L'), Node(1, 'E'), Node(1, 'O'), Node(1, 'R'),
             Node(2, 'I')]
    huffmanTree = build(nodes)
    print(huffmanTree.key)
